package org.hot100_1;

public class leetcode68 {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
//        int [] helper = new int[n];
//        split(nums,0,n-1,helper);
//        return helper[n-k];
        QuickSort(nums,0,n-1);
        return nums[n-k];
    }

    private void QuickSort(int [] nums,int left,int right){
        if (left>=right){
            return;
        }

        int v = nums[left];

        int lt = left;
        int gt = right+1;

        int i =left+1;

        while (i<gt){
            if (nums[i]>v){
                swap(nums,i,gt-1);
                gt--;
            }else if (nums[i]<v){
                swap(nums,i,lt+1);
                lt++;
                i++;
            }else {
                i++;
            }
        }

        swap(nums,left,lt);
        QuickSort(nums,left,lt-1);
        QuickSort(nums,gt,right);

    }

    private void swap(int [] array,int n1,int n2){
        if (n1==n2){
            return;
        }
        int temp = array[n1];
        array[n1]=array[n2];
        array[n2]=temp;
    }

    //[left,right]
    private void split(int [] nums,int left,int right,int [] helper){

        if (left==right){
            return;
        }

        int mid = (left+right)>>>1;
        split(nums,left,mid,helper);
        split(nums,mid+1,right,helper);
        merge(nums,left,mid,mid+1,right,helper);
        System.arraycopy(helper,left,nums,left,right-left+1);
    }

    private void merge(int [] nums,int leftStart,int leftEnd,int rightStart,int rightEnd,int [] helper){

        int curr = leftStart;

        while (leftStart<=leftEnd && rightStart<=rightEnd){
            if (nums[leftStart]<nums[rightStart]){
                helper[curr]=nums[leftStart];
                leftStart++;
            }else {
                helper[curr]=nums[rightStart];
                rightStart++;
            }
            curr++;
        }

        if (leftStart>leftEnd){
            System.arraycopy(nums,rightStart,helper,curr,rightEnd-rightStart+1);

        }

        if (rightStart>rightEnd){
            System.arraycopy(nums,leftStart,helper,curr,leftEnd-leftStart+1);

        }
    }

    public static void main(String[] args) {
        leetcode68 test = new leetcode68();
        int [] array ={3,2,1,5,6,4};
        int kthLargest = test.findKthLargest(array, 2);
        System.out.println(kthLargest);
    }
}
